The present invention relates to data transmission in communication systems, such as the recording and reproduction of binary data in disk storage systems for digital computers, particularly to a cost-effective, high-throughput enumerative encoder/decoder (ENDEC) for encoding/decoding a data stream using a plurality of segmented compare tables representing the full compare table of an enumerative trellis.
This application includes a microfiche appendix of 1 microfiche comprising 50 frames.
Communication systems generally employ a channel code in order to increase the effective signal-to-noise ratio (SNR), thereby increasing the transmission speed while maintaining some arbitrarily low bit error rate. As illustrated in FIG. 1, an encoder 2 encodes an input data stream 4 into an encoded data stream 6 which is then transmitted through a communication channel 8 (e.g,. recorded to a disk). At the receiving end, a decoder 10 decodes the received data stream 12 into decoded output data 14, wherein noise in the communication channel 8 may induce errors in the decoded output data 14. Encoding the input data stream 4 before transmission decreases the bit error rate by increasing noise immunity (increasing the effective SNR). In magnetic disk storage systems, for example, a run-length limited (RLL) channel code is typically employed to limit the spacing between consecutive medium transitions as well as to constrain the maximum spacing between consecutive medium transitions (i.e., constrain the minimum and maximum number of xe2x80x9c0xe2x80x9d bits between xe2x80x9c1xe2x80x9d bits in NRZI recording). The first constraint (the xe2x80x9cdxe2x80x9d constraint) increases the effective SNR by attenuating intersymbol interference (ISI). The second constraint (the xe2x80x9ckxe2x80x9d constraint) increases the effective SNR by increasing the accuracy of the phase error estimate in the timing recovery phase-locked loop. Other constraints may also be implemented by the channel code; for example, a maximum transition run-length (MTR) limits the maximum number of consecutive medium transitions which increases the effective SNR by xe2x80x9ccoding outxe2x80x9d certain dominant error events from a trellis sequence detector.
Encoding the input data stream to satisfy a given set of code constraints requires that a certain number of redundancy bits be added to the transmitted (recorded) data stream. The redundancy bits decrease the transmission rate (storage density) by increasing the total number of bits which must be transmitted for every uncoded bit. This is generally referred to as the xe2x80x9ccode ratexe2x80x9d and is denoted by the ratio m/n where m represents the number of unencoded bits and n represents the number of encoded bits. Employing a channel code allows for an increase in the transmission rate (storage capacity) only if the code rate is sufficiently large; however, maximizing the code rate often means increasing the cost and complexity of the ENDEC circuitry. Thus, significant effort is spent on designing channel codes which exhibit a high code rate while minimizing the cost and complexity of the ENDEC circuitry.
One known method for implementing a channel ENDEC which provides relatively high code rates with nominal cost and complexity is a technique referred to as xe2x80x9cenumerative codingxe2x80x9d. This technique is described in detail by M. Mansuripur in xe2x80x9cEnumerative Modulation Coding with Arbitrary Constraints and Post-Modulation Error Correction Coding for Data Storage Systems,xe2x80x9d SPIE, vol. 1499, Optical Data Storage, 1991, pp. 72-86, the disclosure of which is incorporated herein by reference.
Enumerative codes are essentially block codes wherein an m-bit input block or dataword is encoded into an n-bit output block or codeword. The m-bit input block is viewed as an integer which is processed through an enumerative trellis. Each state in the enumerative trellis is assigned a value representing the number of unique paths through the enumerative trellis starting from that state. The enumerative trellis is derived from a state transition diagram which defines the channel code in terms of the code constraints.
As an example, consider the state transition diagram shown in FIG. 2A which implements a xe2x80x9cQuadbit mod 2xe2x80x9d constraint. The xe2x80x9cQuadbit mod 2xe2x80x9d constraint enhances the operation of a trellis sequence detector by allowing four consecutive medium transitions to occur only if started on every other sample interval, as well as coding out sequences comprising more than four consecutive medium transitions. From the state transition diagram shown in FIG. 2A an enumerative trellis can be constructed for a rate 17/18 channel code as shown in FIG. 2B. The 17/18 enumerative trellis has five states (S0 through S8) wherein state S2 has been selected as both the starting state and the ending state.
During the encoding process, at each state in the enumerative trellis an input value is compared to the state value and an output bit is generated (0 or 1) for the 18-bit output codeword, the bits for which are labeled along the top of the enumerative trellis in FIG. 2B. For example, if the input value is less than the state value a xe2x80x9c0xe2x80x9d bit is generated and the input value is not modified, otherwise a xe2x80x9c1xe2x80x9d bit is generated and the input value is updated by subtracting the state value. The selected branch leads to the next state, wherein another comparison is made and another output bit generated. This process continues until the last state of the enumerative trellis has been reached wherein all 18 bits of the output codeword will have been generated.
The encoding operation with respect to the enumerative trellis of FIG. 2B is further understood by considering the 17-bit input dataword (10000101110011010) which has an integer value of 68506. This is the initial input value compared with the starting state value of 70632 at S2; since 68506 is less than 70632, a xe2x80x9c0xe2x80x9d bit is generated for bit 18 by following the dashed-line branch to state S0 (the input value is not modified). Next, the input value of 68506 is compared to the current state value 35316 at S0; since 68506 is greater than 35316, a xe2x80x9c1xe2x80x9d bit is generated for bit 17 by following the solid-line branch to state S2, and the input value 68506 is modified by subtracting the state value 35316 to generate a next input value of 33190. The new input value 33190 is compared to the state value 18630 at S2; since 33190 is greater than 18630, a xe2x80x9c1xe2x80x9d bit is generated for bit 16 by following the solid-line branch to state S4, and the input value 33190 is modified by subtracting the state value 18630 to generate a next input value of 14560. This process continues until all 18 output bits have been generated and the last state in the enumerative trellis has been reached. For the representative 17-bit input dataword (10000101110011010) the 18-bit output codeword generated by the enumerative trellis of FIG. 2B is (011110000111100001).
Certain of the states in an enumerative trellis may have only one output branch in which case the encoder is forced to output a xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d bit. For example, state S8 in the trellis of FIG. 2B has only one output branch, a dashed-line branch for outputting a xe2x80x9c0xe2x80x9d bit. When this state is reached, the encoder is forced to output a xe2x80x9c0xe2x80x9d bit by following the dashed-line branch to state S2 and the input value is not modified.
When a codeword is received (read from the disk), it is decoded using the same enumerative trellis as that used for encoding. The decoding process is essentially the inverse of the encoding process; that is, an integer representing the decoded dataword is constructed by traversing the trellis in response to the bits in the received codeword starting with the same bit as with the encoding process (the most significant bit). The integer is initialized to zero, and then starting with the first state in the enumerative trellis, the state value is added to the integer if the received bit is a xe2x80x9c1xe2x80x9d bit, otherwise the integer is not modified. The branch corresponding to the received xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d bit is followed in the enumerative trellis to the next state wherein again the state value is added to the integer if the next bit of the received codeword is a xe2x80x9c1xe2x80x9d bit. This process continues until the last state of the enumerative trellis has been reached wherein the resultant integer represents the decoded block.
The decoding process is further understood by considering the how the enumerative trellis of FIG. 2B is used to decode the received codeword (011110000111100001) into an integer value of 68506. Since the first bit of the received codeword (the most significant bit) is a xe2x80x9c0xe2x80x9d bit, the state value 70632 for the starting state (state S2) is not added to the integer and the dashed-line branch is followed to the next state (state S0). Since the next bit of the received codeword is a xe2x80x9c1xe2x80x9d bit, the state value 35316 at S0 is added to the integer and the solid-line branch is followed to the next state (state S2). This process continues until the last state of the enumerative trellis has been reached wherein the integer will have a value of 68506.
In many communication systems, particularly disk storage systems, the throughput of the channel is of critical concern. Thus, in addition to the need for a cost-effective implementation for an enumerative ENDEC, there is a need for an enumerative ENDEC which exhibits high throughput so as not to slow the operation of the channel.
The present invention may be regarded as a cost-effective high-throughput enumerative encoder for encoding m-bit input datawords in an input data stream into n-bit output codewords in an encoded output data stream for use in a communication channel. The enumerative encoder comprises an input buffer for storing a plurality of bits in the input data stream, and a plurality of segmented compare tables for encoding the bits stored in the input buffer into the encoded output data stream, wherein each segmented compare table represents a segment of a full compare table of an enumerative trellis.
The present invention may also be regarded as a cost-effective high-throughput enumerative decoder for decoding n-bit input codewords in a received data stream into m-bit output datawords in a decoded data stream for use in a communication channel. The enumerative decoder comprises an input buffer for storing a plurality of bits in the received data stream, and a plurality of segmented compare tables for decoding the bits stored in the input buffer into the decoded data stream, wherein each segmented compare table represents a segment of a full compare table of an enumerative trellis.